// 如果需要遍历整颗树，递归函数就不能有返回值。
// 如果需要遍历某一条固定路线，递归函数就一定要有返回值！
class Solution {
 public:
  /*
  int findBottomLeftValue(TreeNode* root) {
      queue<TreeNode*> que;
      if (root != NULL) que.push(root);
      int result = 0;
      while (!que.empty()) {
          int size = que.size();
          for (int i = 0; i < size; i++) {
              TreeNode* node = que.front();
              que.pop();
              if (i == 0) result = node->val;  // 记录最后一行第一个元素
              if (node->left) que.push(node->left);
              if (node->right) que.push(node->right);
          }
      }
      return result;
  }
  */
  // int maxLen = 0;
  int maxLen = INT_MIN;  // *****************
  int maxleftValue = 0;
  int findBottomLeftValue(TreeNode* root) {
    traversal(root, 0);
    return maxleftValue;
  }
  void traversal(TreeNode* root, int leftLen) {
    if (root->left == NULL && root->right == NULL) {
      if (leftLen > maxLen) {
        maxLen = leftLen;
        maxleftValue = root->val;
      }
      return;
    }
    if (root->left) {
      leftLen++;
      traversal(root->left, leftLen);
      leftLen--;  // 回溯
    }
    if (root->right) {
      leftLen++;
      traversal(root->right, leftLen);
      leftLen--;  // 回溯
    }
    return;
  }
};